\section{Proofs of Lemma~\ref{lem:finish_charging_scheme} and Invariant~\ref{inv:main}}
\label{sec:proofs}%
We finish the analysis by showing that Invariant~\ref{inv:main} and
Lemma~\ref{lem:finish_charging_scheme} are satisfied. To reduce
complication of the argument, we note the following lemma.

\begin{lemma}
We may assume that all vertices $u, v, u', v'$ (defined in the {\sc
Move-Charge} algorithm) are distinct.
\end{lemma}
\begin{proof}
If $v=v'$ then $G$ contains a loop. If $u=v'$ then $e^1$ is a
multiplication of $e$. Since $e^1$ replaces $e$, $w(e^1)\geq w(e)$.
We deal with this case by setting $ch_{\tau+1}(e^1):=ch_\tau(e)$,
$ch_{\tau+1}(u):=ch_\tau(u)$, $ch_{\tau+1}(v):=ch_\tau(v)$, and
$ch_\tau(e) = ch_\tau(u) = ch_\tau(v) := 0$. Clearly, the invariants
above holds. Each of other cases is similar to one of the previous
two cases. 
%\qed
\end{proof}


First, we prove Lemma~\ref{lem:finish_charging_scheme},
Invariant~\ref{inv:main}(\ref{inv:charge_on_matching_only}), and
Invariant~\ref{inv:main}(\ref{inv:unique_time}) which easily follows
from the charging scheme.
%
Since the {\sc Move-Charge} algorithm sets the value of $ch_t(x)=0$
for all $x\in V(G)\cup E(G)$ and all $t<m$,
Lemma~\ref{lem:finish_charging_scheme} is satisfied. Moreover,
because we always move charge to edges in a matching, the
Invariant~\ref{inv:main}(\ref{inv:charge_on_matching_only}) is
satisfied. Finally, Invariant~\ref{inv:main}(\ref{inv:unique_time})
can be seen as charge on edges is always moved from time $\tau$ to
time $\tau+1$ while we put charge on a vertex $v$ at time $\tau$
only if there is charge on $v$ at time $\tau-1$ or there is an edge
in $OPT$ that put charge on $v$ at time $\tau$.

We now show that the rest conditions in invariant~\ref{inv:main} are
satisfied in the following sections.

\subsection{Proof of Invariant~\ref{inv:main}(\ref{inv:charge_more_than_opt})}
To show that
Invariant~\ref{inv:main}(\ref{inv:charge_more_than_opt}) always
holds, it is enough to show that no charge is lost in the {\sc
Move-Charge} procedure. In other words, the charge we add is more
than the original charge (which, in all cases except Case~3.2.2, is
$ch_\tau(u)+ch_\tau(v)+ch_\tau(uv)$). We first note the following
inequalities which are easy to verify and will be used them over and
over.

\begin{lemma}\label{lem:alpha_beta_gamma_ineq}\hfill
\begin{eqnarray}
\label{eqn:first} \alpha\gamma &\geq& \alpha+\gamma\\
\label{eqn:second} \beta\gamma &\geq& \alpha\\
\label{eqn:third} 1+\beta\gamma &\geq& \alpha+\gamma
%ACTUALLY!!!! THE FIRST AND THE LAST ARE EQUALITIES *******************************
%\label{eqn:fourth} \beta\gamma+\gamma^2+\frac{1}{\gamma^2} &\geq&
%2\gamma+\beta
\end{eqnarray}
\end{lemma}
%\begin{proof}
%Trivial.
%\end{proof}

From this lemma, we can prove the
Invariant~\ref{inv:main}(\ref{inv:charge_limit}) by case analysis.
This step is easy but tedious. We only give an important case which
is Case~3.2.1 here. The rest can be found in
Appendix~\ref{app:proof_charge_limit}.

%
%Now we show that no charge is lost, case by case. In all cases we
%assume that the Invariant~\ref{inv:main}(\ref{inv:charge_limit}) is
%satisfied at time $\tau$.

\begin{description}
  \item[Case 3.2.1] Let $u_{k+1}, v_k, u_k, ... , v_1, u_1, v_0, v'_0, u'_1, v'_1,
   ..., u'_k, v'_k, u'_{k'+1}$ be the charging chain at time $\tau'$
   as in Algorithm~\ref{alg:move_charge}. The total charge that the
   algorithm removes (in the last step) is
   $w(v_0v'_0) + \sum_{i=1}^k (ch_{\tau} +
   ch_\tau(u_i)+ch_\tau(v_i)) \nonumber
   \leq
   w(v_0v'_0) + \sum_{i=1}^k (\alpha + 0 + \gamma)w(u_iv_i)$ while the total new charge
   the algorithm adds is
   $\sum_{i=1}^k \beta\gamma (f_\tau(u_i)+f_\tau(v_i))w(u_iv_i)+\sum_{i=1}^k
   \gamma w(v_iu_{i+1}).$
   Since the optimal edge $v_0v'_0$ is not
   added, $w(v_0v'_0)+\sum_{i=1}^k w(u_iv_i) \leq \gamma\sum_{i=0}^k
   w(v_iu_{i+1}).$ Using, $w(v_0v'_0) \leq \gamma\sum_{i=0}^k
   w(v_iu_{i+1}) - \sum_{i=1}^k w(u_iv_i)$, the total removed charge is
   at most $$\gamma\sum_{i=0}^k w(v_iu_{i+1})
   + \sum_{i=1}^k (\alpha + \gamma -1 )w(u_iv_i)$$ which is at most
   the total newly added charge by Inequality~\eqref{eqn:third}.
\end{description}



\subsection{Proof of Invariant~\ref{inv:main}(\ref{inv:charge_limit})}%
Due to space limitation, we only outline the proof here and place
the full proof in Appendix~\ref{app:proof_of_inv}. The idea of the
proof is that all cases except Case 3.2 gives charge not too much
and the invariant is easily maintained. The only complication is
when Case 3.2 involves. In particular, when both Case 3.2.1 and
3.2.2 put charge at the same edge, the total charge could exceed the
limitation. However, we show that this is impossible. In particular,
we show that an end of any charging chain can be assumed to be a
shadow edge with no charge on the vertex that is not in the chain.
This prevents such shadow edge to use Case 3.2.2. The main reason of
this is that we extend the charging scheme as long as such shadow
edge is not found. The only complication is when the shadow edge
creates a loop. However, we show that the claim still hold in this
case.
